package uestc.lj.advanced.dp;

/**
 * 判定一个由[a-z]字符构成的字符串和一个包含'.'和'*'通配符的字符串是否匹配
 * '.' 匹配任意单一字符。
 * '*' 匹配任意多个字符包括0个字符
 *
 * @Author:Crazlee
 * @Date:2021/12/10
 */
public class Code11_RegularExpressionMatch {

	public static boolean isValid(char[] s, char[] e) {
		// 原始串不允许出现 '*' 和 '.'
		for (char c : s) {
			if (c == '*' || c == '.') {
				return false;
			}
		}
		// 表达式串中'*'前面必须有字符并且两个'*'不能紧邻
		for (int i = 0; i < e.length; i++) {
			if (e[i] == '*' && (i == 0 || e[i - 1] == '*')) {
				return false;
			}
		}
		return true;
	}


	public static boolean isMatch(String str, String exp) {
		if (str == null || exp == null) {
			return false;
		}
		char[] s = str.toCharArray();
		char[] e = exp.toCharArray();
		return isValid(s, e) && process(s, e, 0, 0);
	}

	/**
	 * s[si...]——e[ei...]
	 * 看能否匹配
	 * 保证ei位置不是*
	 *
	 * @param s  原字符串
	 * @param e  表达式串
	 * @param si 原字符串的索引
	 * @param ei 表达式串的索引
	 * @return 能否匹配
	 */
	private static boolean process(char[] s, char[] e, int si, int ei) {
		if (ei == e.length) {
			return si == s.length;
		}
		// ei+1位置不是*, str[si]必须和 exp[ei]匹配并且后续也能走通
		if (ei + 1 == e.length || e[ei + 1] != '*') {
			return si != s.length && (e[ei] == s[si] || e[ei] == '.') && process(s, e, si + 1, ei + 1);
		}

		//ei+1位置是*
		while (si != s.length && (e[ei] == s[si] || e[ei] == '.')) {
			// 相当于添加一个s[si]
			if (process(s, e, si, ei + 2)) {
				return true;
			}
			si++;
		}
		return process(s, e, si, ei + 2);
	}

	//================================================================================================================

	public static boolean isMatchDP(String str, String exp) {
		if (str == null || exp == null) {
			return false;
		}
		char[] s = str.toCharArray();
		char[] e = exp.toCharArray();
		if (!isValid(s, e)) {
			return false;
		}
		boolean[][] dp = initDPMap(s, e);
		for (int i = s.length - 1; i > -1; i--) {
			for (int j = e.length - 2; j > -1; j--) {
				if (e[j + 1] != '*') {
					dp[i][j] = (s[i] == e[j] || e[j] == '.') && dp[i + 1][j + 1];
				} else {
					int si = i;
					while (si != s.length && (s[si] == e[j] || e[j] == '.')) {
						if (dp[si][j + 2]) {
							dp[i][j] = true;
							break;
						}
						si++;
					}
					if (!dp[i][j]) {
						dp[i][j] = dp[si][j + 2];
					}
				}
			}
		}
		return dp[0][0];
	}

	public static boolean[][] initDPMap(char[] s, char[] e) {
		int slen = s.length;
		int elen = e.length;
		boolean[][] dp = new boolean[slen + 1][elen + 1];
		dp[slen][elen] = true;
		for (int j = elen - 2; j > -1; j = j - 2) {
			if (e[j] != '*' && e[j + 1] == '*') {
				dp[slen][j] = true;
			} else {
				break;
			}
		}
		if (slen > 0 && elen > 0) {
			if ((e[elen - 1] == '.' || s[slen - 1] == e[elen - 1])) {
				dp[slen - 1][elen - 1] = true;
			}
		}
		return dp;
	}

	public static void main(String[] args) {
		String str = "abcccdefg";
		String exp = "ab.*d.*e.*";
		System.out.println(isMatch(str, exp));
		System.out.println(isMatchDP(str, exp));
	}
}
